package com.cjm.algorithm.tree;

import com.cjm.algorithm.TreeNode;

import java.util.*;

public class InorderTraversal94 {
    public List<Integer> inorderTraversal(TreeNode root) {
        m3res.clear();
        return m4(root);
    }

    private List<Integer> m4(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> container = new LinkedList<>();
        TreeNode cur = root;
        while (cur != null || !container.isEmpty()) {
            if (cur != null) {
                container.addFirst(cur);
                cur = cur.left;
            } else {
                cur = container.pollFirst();
                res.add(cur.val);
                cur = cur.right;
            }
        }
        return res;
    }


    private List<Integer> m3res = new ArrayList<>();
    public List<Integer> m3(TreeNode root) {
        if (root == null) {
            return m3res;
        }
        if (root.left!= null) {
            m3(root.left);
        }
        m3res.add(root.val);
        if (root.right != null) {
            m3(root.right);
        }
        return m3res;
    }


    private static List<Integer> m2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> nodes = new Stack<>();
        // 一来， 先将根节点放入到栈中去
        if (root != null) nodes.add(root);
        while (!nodes.isEmpty()) {
            // 拿出栈顶的元素
            TreeNode top = nodes.peek();
            if (top != null) {
                // 先将这个栈顶元素弹出， 避免重复操作， 再将右中左元素放入到栈中去
                nodes.pop();
                // 将右儿子放入到栈中
                if (top.right != null) nodes.add(top.right);
                // 再将中间节点放入到栈中
                nodes.add(top);
                // 加入一个空, 为什么呢？中间节点访问过， 但是没有处理， 这里加一个null标记一下， 说这种也是一种方法
                nodes.add(null);
                // 将左儿子放入到栈中去
                if (top.left != null) nodes.add(top.left);
            } else {
                // 如果栈顶的元素为空
                nodes.pop();
                // 那么说明下一个元素是应该放入到结果集中的
                top = nodes.pop();
                // 放入到结果集中去
                res.add(top.val);
            }
        }
        return res;
    }

    private static List<Integer> m1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                TreeNode pop = stack.pop();
                if (pop != null) {
                    res.add(pop.val);
                    current = pop.right;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.add(1);
        stack.add(2);
        stack.add(3);
        stack.clear();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.err.println("OK");
    }
}
